package com.jml.算法;


import java.util.HashMap;
import java.util.Map;
import org.junit.Test;

/**
 * @author:jml
 * @date: 2020/3/30 0030 22:07
 * @description：
  * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
  *
 * 示例 1:
 * 输入: "dvdf"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "vdf"，所以其长度为 3。
 *
 *abba
 * 应该为2
 *
  * 示例 1:
  * 输入: "abcabcbb"
  * 输出: 3
  * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
  *
  * 示例 2:
  * 输入: "bbbbb"
  * 输出: 1
  * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
  *
  * 示例 3:
  * 输入: "pwwkew"
  * 输出: 3
  * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
  *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
  *
  * 来源：力扣（LeetCode）
  * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
  * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 无重复字符的最长子串 {

    /**
     * 滑动窗口计数法，两个索引都不能回退
     *
     *  我们定义不重复子串的开始位置为 start，结束位置为 end
     * 随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，value是字符索引，获取其 value值然后将value+1，并这个值更新到start，
     *  此时 [start, end] 区间内不存在重复字符
     *
     */
    @Test
    public void my(){
         String s = "abba";
         int start =0 ;
         int sum = 0;
         Map<Character,Integer> map = new HashMap();
         for (int end = 0; end < s.length(); end++) {
             if(map.containsKey(s.charAt(end))){
                 //必须要取最大的start，当end=第二个a   如果不取最大start就在第一个(a+1)=第一个b，从第二个b的位置回退了，此时这个区间是不准确的，start不能回退
                 // 导致了start的值变小了,就会造成bba，这是个重复串，还是有问题
                 // //如果不加1，pww--> 当end在第二个w， 此时start在第一个w，此时是不正确的，因为连续的w是重复的
                 start = Math.max(map.get(s.charAt(end))+1, start);
             }
             //end - start + 1,表示两个索引之间差多少字符，因为本身占有的字符也算，所以要+1
             //比如，start和end指同一个元素，相减为0，但是本身就可以作为一个字符串应该为1
             //比如，start=0和end=1，相减为1，但是0,1两个元素应该为2 
             sum = Math.max(sum,end-start+1);
             map.put(s.charAt(end),end);
         }
         System.out.println(sum);
     }


     @Test
    public void other(){
         String s = "pwwwkew";
         int n = s.length(), ans = 0;
         Map<Character, Integer> map = new HashMap<>();
         int start = 0;
         for (int end = 0; end < n; end++) {
             if (map.containsKey(s.charAt(end))) {
                 /*我们定义不重复子串的开始位置为 start，结束位置为 end
                    *随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，
                    * 此时 [start, end] 区间内不存在重复字符
                    */
                 start = map.get(s.charAt(end));
                 //start = Math.max(map.get(s.charAt(end)), start);
             }
             //end - start + 1,表示两个索引之间差多少字符，因为本身占有的字符也算，所以要+1
             //比如，start和end指同一个元素，相减为0，但是本身就可以作为一个字符串应该为1
             //比如，start=0和end=1，相减为1，但是0,1两个元素应该为2
             //ans就是每过一个字符就计算一下间距
             ans = Math.max(ans, end - start + 1);
             //key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复,不重复的位置
             //start重置的时候不会再重复元素的位置，会在重复元素后面的位置
             //如果不加1，pww--> start在第一个w，end在第二个w，此时是不正确的，因为连续的w是重复的
             //这里加
             map.put(s.charAt(end), end + 1);
         }
         System.out.println(ans);
     }



}
